// 2779. 数组的最大美丽值
/**
 * 2779. 数组的最大美丽值
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中，你可以执行下述指令：

在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。
数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。

注意：你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

## 示例 1：
输入：nums = [4,6,1,2], k = 2
输出：3
解释：在这个示例中，我们执行下述操作：
- 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
> 注：下标1为6，所以选择范围是[6-2,6+2] => [4,8]
> 注：[4,6,1,2]能改为[3,5,3,3]，即每个数都和原来数组不一样也是可以的，但美丽值仍然是3

- 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
> 注：下标3为2，所以选择范围是[2-2,2+2] => [0,4]

执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

## 示例 2：
输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function (nums, k) {
    /**
     * 思路：
     * 刨去美丽数的概念，这道题就是求数组中，每一位上能出现的同一个数字的最大次数
     * 最简单的方法，可以使用一张表，作用是记录每一个数字出现的次数，最后出现最多的次数就是美丽值
     * 当轮询数组的每一位时，将这一位上所有可能出现的数字的值都登记到表上，但这样大概率会超时
     *
     * 换种思路，美丽值的最大数，意味着数组中的某几个元素，可以互相变换成一致的，那如果现将所有数排序排好，记录每个数的值域能覆盖的数值范围，是不是也是美丽数？
     *  */

    nums.sort((a, b) => a - b);
    // 双指针i,j i和j框定的范围为一组美丽数的值

    let maxCount = 1;
    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (nums[i] + 2 * k >= nums[j]) {
            maxCount = Math.max(maxCount, j - i + 1);
        } else {
            i++;
        }
    }

    return maxCount;
};

function t(nums, k) {
    console.log(`${JSON.stringify(nums)}, ${k} is: ${maximumBeauty(nums, k)}`);
}

t([4, 6, 1, 2], 2); // 3
t([1, 1, 1, 1], 10); // 4
t([5, 57, 46], 15); // 2

/**
 * 思路
 * 这是一种平均值，平均值4舍五入，然后依次看每个值是否能达到平均值
 *
 * 但这没法通过测试用例：
 * t([5, 57, 46], 15);
 */
// var maximumBeauty = function (nums, k) {
//     /**
//      * 思路：
//      * 刨去美丽数的概念，这道题就是求数组中，每一位上能出现的同一个数字的最大次数
//      * 最简单的方法，可以使用一张表，作用是记录每一个数字出现的次数，最后出现最多的次数就是美丽值
//      * 当轮询数组的每一位时，将这一位上所有可能出现的数字的值都登记到表上
//      *  */

//     const sum = nums.reduce((a, b) => a + b, 0);
//     const average = Math.round(sum / nums.length);

//     let count = 0;

//     nums.forEach((i) => {
//         if (i - k <= average && i + k >= average) {
//             count++;
//         }
//     });

//     // 如果count为0，证明每个数都里平均值很远，但美丽值不可能为0，最小为1，此时返回1
//     return count === 0 ? 1 : count;
// };
